今天繼續寫鏈表，整理幾題比較需要思考的題目，直接進例題
鏈表的題目沒什麼模板或是固定思路..所以就放幾題經典的

例題實戰

138. 复制带随机指针的链表
往前複製一份再斷開~~不算很直觀

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr){
            return nullptr;
        }
        //每個Node複製一份
        Node* curr = head;
        while(curr){
            Node* copy = new Node(curr->val);
            Node* nnext = curr->next;
            curr->next = copy;
            copy->next = nnext;
            curr = curr->next->next;
        }
        curr = head;
        //鏈random指針
        while(curr){
            Node* copy = curr->next;
            if(copy&&curr->random)
                copy->random = curr->random->next;
            curr = curr->next->next;
        }
        //分離
        curr = head;
        Node* new_head = head->next;
        while(curr->next->next){
            Node* old = curr;
            Node* nnew = curr->next;
            old->next = old->next->next;
            nnew->next = nnew->next->next;
            curr = old->next;
        }
        curr->next->next = nullptr;
        curr->next = nullptr;
        return new_head;
    }
};

142. 环形链表 II
判斷有環無環也算很經典的問題吧(?
但解決方法很簡單，這類問題就用一個快指針(一次移動兩步)，一個慢指針(一次移動一步)，看最後快指針能不能倒追到慢指針(就有環)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    // ListNode* res;
    // unordered_map<ListNode*, bool> hash;
public:
    ListNode *detectCycle(ListNode *head) {
        // if(dfs(head)==false){
        //     return NULL;
        // }
        // return res;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!=NULL && fast->next!=NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow==fast){
                ListNode* p = head;
                while(p!=slow){
                    p = p->next;
                    slow = slow->next;
                }
                return p;
            }
        }
        return NULL;
    }
    // bool dfs(ListNode* head){
    //     if(head==NULL || head->next ==  NULL){
    //         return NULL;
    //     }
    //     if(hash[head]!=NULL){
    //         res = head;
    //         return true;
    //     }
    //     else{
    //         cout<< hash[head];
    //         hash[head] = true;
    //         return dfs(head->next);
    //     }
    //     return false;
    // }
};

19. 删除链表的倒数第 N 个结点
倒數N就先讓一個指針先跑N步另一個從起點出發，等前面的指針走到終點，就是倒數N了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //雙指針
        ListNode* temp = head;
        ListNode* f = head;
        ListNode* s = head;
        while(n--){
            f = f->next;
        }
        if(f==NULL){
            return head->next;
        }
        while(f->next!=NULL){
            f = f->next;
            s = s->next;
        }
        s->next = s->next->next;
        return temp;
    }
};